package Test;

import java.util.List;

public class 升序排序链表 {
    public ListNode sortList(ListNode head) {
        return head==null?head:mergeList(head);
    }

    ListNode mergeList(ListNode head){
        if(head==null) return head;
        ListNode slow,pre,fast;
        slow=fast=head;
        pre=null;
        while (fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        ListNode a=mergeList(head);
        ListNode b=mergeList(pre);
        return merge(a,b);
    }
    ListNode merge(ListNode a,ListNode b){
        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        while (a!=null&&b!=null){
            if(a.val<b.val){
                cur.next=a;
                a=a.next;
            }else {
                cur.next=b;
                b=b.next;
            }
            cur=cur.next;
        }
        if(a!=null){
            cur.next=a;
        }
        if(b!=null){
            cur.next=b;
        }
        return dummy.next;
    }

}
